Find Minimum in Rotated Sorted Array || Search in Rotated Sorted Array || Search in Rotated Sorted Array II

发表于

Find Minimum in Rotated Sorted Array

Question

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Analysis

Compact and clean C++ solution

  • left<right 当前left即最小值
  • 否则一直二分，直至循环结束所得的left为结果
  • 循环条件为left<right，当left=right时进入循环，所得mid可能等于left，则数组越界 e.g.：[1]
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int findMin(int[] nums) {
        int left=0;
        int right=nums.length-1;
        while(left<right){
            if(nums[left]<nums[right])
                return nums[left];
            int mid=(left+right)/2;
            if(nums[left]<=nums[mid])
                left=mid+1;
            else
                right=mid;
        }
        return nums[left];
    }
}

Search in Rotated Sorted Array

Question

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Analysis

Concise O(log N) Binary search solution

  • 在找到位移后，虽然每次同realmid比值，但是在对left和right操作的过程中始终用的是mid的值

Revised Binary Search

  • 在最后循环结束且没有返回结果的时候，需要比较此时left的值是否等于target
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        int shift=0;
        while(left<right){
            if(nums[left]<nums[right])  break;
            int mid=(left+right)/2;
            if(nums[left]<=nums[mid])  left=mid+1;
            else    right=mid;
        }
        shift=left;
        
        left=0;
        right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            int realmid=(mid+shift)%nums.length;
            if(target==nums[realmid])   return realmid;
            else if(target>nums[realmid])   left=mid+1;
            else    right=mid-1;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]==target)
                return mid;
            if(nums[left]<=nums[mid]){
                if(target<nums[mid]&&target>=nums[left])
                    right=mid-1;
                else
                    left=mid+1;
            }else{
                if(target>nums[mid]&&target<=nums[right])
                    left=mid+1;
                else
                    right=mid-1;
            }
        }
        if(nums[left]==target)
            return left;
        return -1;
    }
}

Search in Rotated Sorted Array II

Question

Follow up for “Search in Rotated Sorted Array”:

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

Analysis

When there are duplicates, the worst case is O(n). Could we do better?

  • A[left]=A[mid]：可能从left到right所有的元素都是相同的；或者不同的数字（可能包含target）存在于left到right之间，但是无法判断是哪种情况，所以每次将left向右挪一位再继续
  • 当A[left]<A[mid]时，代表mid左侧是已经排好序的，反之右侧已经排好序
  • 假如target位于当前排好序的区间内，则将mid值赋给left或right
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public boolean search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]==target)
                return true;
            else if(nums[left]<nums[mid]){
                if(target<nums[mid]&&target>=nums[left])
                    right=mid-1;
                else
                    left=mid+1;
            }else if(nums[left]>nums[mid]){
                if(target>nums[mid]&&target<=nums[right])
                    left=mid+1;
                else
                    right=mid-1;
            }else
                left++;
        }
        return false;
    }
}